#include <pmm.h>
#include <list.h>
#include <string.h>
#include <default_pmm.h>

/* In the first fit algorithm, the allocator keeps a list of free blocks (known as the free list) and,
   on receiving a request for memory, scans along the list for the first block that is large enough to
   satisfy the request. If the chosen block is significantly larger than that requested, then it is 
   usually split, and the remainder added to the list as another free block.
   Please see Page 196~198, Section 8.2 of Yan Wei Min's chinese book "Data Structure -- C programming language"
*/
// you should rewrite functions: default_init,default_init_memmap,default_alloc_pages, default_free_pages.
/*
 * Details of FFMA
 * (1) Prepare: In order to implement the First-Fit Mem Alloc (FFMA), we should manage the free mem block use some list.
 *              The struct free_area_t is used for the management of free mem blocks. At first you should
 *              be familiar to the struct list in list.h. struct list is a simple doubly linked list implementation.
 *              You should know howto USE: list_init, list_add(list_add_after), list_add_before, list_del, list_next, list_prev
 *              Another tricky method is to transform a general list struct to a special struct (such as struct page):
 *              you can find some MACRO: le2page (in memlayout.h), (in future labs: le2vma (in vmm.h), le2proc (in proc.h),etc.)
 * (2) default_init: you can reuse the  demo default_init fun to init the free_list and set nr_free to 0.
 *              free_list is used to record the free mem blocks. nr_free is the total number for free mem blocks.
 * (3) default_init_memmap:  CALL GRAPH: kern_init --> pmm_init-->page_init-->init_memmap--> pmm_manager->init_memmap
 *              This fun is used to init a free block (with parameter: addr_base, page_number).
 *              First you should init each page (in memlayout.h) in this free block, include:
 *                  p->flags should be set bit PG_property (means this page is valid. In pmm_init fun (in pmm.c),
 *                  the bit PG_reserved is setted in p->flags)
 *                  if this page  is free and is not the first page of free block, p->property should be set to 0.
 *                  if this page  is free and is the first page of free block, p->property should be set to total num of block.
 *                  p->ref should be 0, because now p is free and no reference.
 *                  We can use p->page_link to link this page to free_list, (such as: list_add_before(&free_list, &(p->page_link)); )
 *              Finally, we should sum the number of free mem block: nr_free+=n
 * (4) default_alloc_pages: search find a first free block (block size >=n) in free list and reszie the free block, return the addr
 *              of malloced block.
 *              (4.1) So you should search freelist like this:
 *                       list_entry_t le = &free_list;
 *                       while((le=list_next(le)) != &free_list) {
 *                       ....
 *                 (4.1.1) In while loop, get the struct page and check the p->property (record the num of free block) >=n?
 *                       struct Page *p = le2page(le, page_link);
 *                       if(p->property >= n){ ...
 *                 (4.1.2) If we find this p, then it' means we find a free block(block size >=n), and the first n pages can be malloced.
 *                     Some flag bits of this page should be setted: PG_reserved =1, PG_property =0
 *                     unlink the pages from free_list
 *                     (4.1.2.1) If (p->property >n), we should re-caluclate number of the the rest of this free block,
 *                           (such as: le2page(le,page_link))->property = p->property - n;)
 *                 (4.1.3)  re-caluclate nr_free (number of the the rest of all free block)
 *                 (4.1.4)  return p
 *               (4.2) If we can not find a free block (block size >=n), then return NULL
 * (5) default_free_pages: relink the pages into  free list, maybe merge small free blocks into big free blocks.
 *               (5.1) according the base addr of withdrawed blocks, search free list, find the correct position
 *                     (from low to high addr), and insert the pages. (may use list_next, le2page, list_add_before)
 *               (5.2) reset the fields of pages, such as p->ref, p->flags (PageProperty)
 *               (5.3) try to merge low addr or high addr blocks. Notice: should change some pages's p->property correctly.
 */
free_area_t free_area;

#define free_list (free_area.free_list)
#define nr_free (free_area.nr_free)

static void
default_init(void) {
    list_init(&free_list);
    nr_free = 0;
}

// base是free_mem的首地址
static void
default_init_memmap(struct Page *base, size_t n) {
    assert(n > 0);
    struct Page *p = base;
    for (; p != base + n; p ++) {
        // 初始将所有页都设为保留态
        assert(PageReserved(p));
        // 三个标志都设为0

        //if this page  is free and is not the first page of free block, 
        //  p->property should be set to 0.
        p->flags = p->property = 0;
        set_page_ref(p, 0);
    }

    // if this page  is free and is the first page of free block, 
    // p->property should be set to total num of block.

    base->property = n;
    SetPageProperty(base); // 要开始使用base页了
    nr_free += n; // 空闲页个数

    // We can use p->page_link to link this page to free_list, (such as: list_add_before(&free_list, &(p->page_link)); )

    // 下面的操作是想把base插入free_list
    // 空闲链表为空
    if (list_empty(&free_list)) {
        list_add(&free_list, &(base->page_link));
        // base直接添到freelist里面
    } else {
        // 不为空时，需要升序
        list_entry_t* le = &free_list;
        // 遍历free_list的所有页
        while ((le = list_next(le)) != &free_list) {
            // 跳出循环说明顺序OK
            struct Page* page = le2page(le, page_link); // 链表->页
            // 若页号较小->位置需要提前
            if (base < page) {
                list_add_before(le, &(base->page_link));
                break;
            } else if (list_next(le) == &free_list) {
                list_add(le, &(base->page_link));
            }// 到尾端还是没有找到合适的位置->插入尾端
        }
    }
}

// 需要分配n张物理页
static struct Page *
default_alloc_pages(size_t n) {
    assert(n > 0);
    // 分配页数>现有页数
    if (n > nr_free) {
        return NULL;
    }
    struct Page *page = NULL;
    list_entry_t *le = &free_list;
    // 顺序遍历free_list中的块
    while ((le = list_next(le)) != &free_list) {
        struct Page *p = le2page(le, page_link);
        // first-fit就停
        if (p->property >= n) {
            page = p;
            break;
        }
    }
    // 找到了合适的页
    if (page != NULL) {
        list_entry_t* prev = list_prev(&(page->page_link));
        list_del(&(page->page_link)); // 删掉page
        // If (p->property >n), we should re-caluclate number of the the rest of this free block
        if (page->property > n) {
            struct Page *p = page + n; // 页号+n
            p->property = page->property - n; // 块中页数-n
            SetPageProperty(p);
            list_add(prev, &(p->page_link)); // 再添到列表
        }
        nr_free -= n; // 空闲页数-n
        ClearPageProperty(page); // Page清理
    }
    return page;
}

// 需要释放，起始地址base
static void
default_free_pages(struct Page *base, size_t n) {
    assert(n > 0);
    struct Page *p = base;
    // 从base开始遍历n张页
    // reset the fields of pages, such as p->ref, p->flags (PageProperty)
    for (; p != base + n; p ++) {
        assert(!PageReserved(p) && !PageProperty(p));
        p->flags = 0;
        set_page_ref(p, 0);
    }
    // base空闲，从该起点开始对应的块连续n张空闲页
    base->property = n;
    SetPageProperty(base);
    nr_free += n;

    // 下面操作和memmap_init中的一样，需要把page加入空闲块的list中
    // 若free_list为空，直接添进去
    if (list_empty(&free_list)) {
        list_add(&free_list, &(base->page_link));
    } else {
        // 若不为空，需要升序排列
        list_entry_t* le = &free_list;
        while ((le = list_next(le)) != &free_list) {
            struct Page* page = le2page(le, page_link);
            if (base < page) {
                list_add_before(le, &(base->page_link));
                break;
            } else if (list_next(le) == &free_list) {
                list_add(le, &(base->page_link));
            } // 若始终找不到合适的位置，直接插入末尾
        }
    }

    // try to merge low addr or high addr blocks. Notice: should change some pages's p->property correctly.
    // 找到base的前一个块le
    list_entry_t* le = list_prev(&(base->page_link));
    if (le != &free_list) {
        p = le2page(le, page_link);
        // 若p和base的空闲页可以连起来
        if (p + p->property == base) {
            // merge
            p->property += base->property;
            ClearPageProperty(base);
            list_del(&(base->page_link));// 删除p
            base = p;
        }
    }

    // 找到base的后一个块le
    le = list_next(&(base->page_link));
    if (le != &free_list) {
        p = le2page(le, page_link);
        if (base + base->property == p) {
            // 从base起始merge
            base->property += p->property;
            ClearPageProperty(p);
            list_del(&(p->page_link));// 删除p
        }
    }
}

static size_t
default_nr_free_pages(void) {
    return nr_free;
}

static void
basic_check(void) {
    // 分配三个页面
    struct Page *p0, *p1, *p2;
    p0 = p1 = p2 = NULL;
    assert((p0 = alloc_page()) != NULL);
    assert((p1 = alloc_page()) != NULL);
    assert((p2 = alloc_page()) != NULL);

    // 确保不相等，引用计数ref也为0
    assert(p0 != p1 && p0 != p2 && p1 != p2);
    assert(page_ref(p0) == 0 && page_ref(p1) == 0 && page_ref(p2) == 0);

    // 页面的物理地址<总物理地址
    assert(page2pa(p0) < npage * PGSIZE);
    assert(page2pa(p1) < npage * PGSIZE);
    assert(page2pa(p2) < npage * PGSIZE);

    // 初始化list并确保为空
    list_entry_t free_list_store = free_list;
    list_init(&free_list);
    assert(list_empty(&free_list));

    // 空闲页数设为0，然后验证不能分配
    unsigned int nr_free_store = nr_free;
    nr_free = 0;

    assert(alloc_page() == NULL);

    // 释放三个页，然后nr_free必为3
    free_page(p0);
    free_page(p1);
    free_page(p2);
    assert(nr_free == 3);

    // 再分配这三个->可
    assert((p0 = alloc_page()) != NULL);
    assert((p1 = alloc_page()) != NULL);
    assert((p2 = alloc_page()) != NULL);

    // 申请分配->不行
    assert(alloc_page() == NULL);

    // 释放p0->list不为空
    free_page(p0);
    assert(!list_empty(&free_list));

    // p0可以分配，分配后不能申请
    struct Page *p;
    assert((p = alloc_page()) == p0);
    assert(alloc_page() == NULL);

    // 空闲页为0
    assert(nr_free == 0);
    // 恢复free_list和nr_free
    free_list = free_list_store;
    nr_free = nr_free_store;

    free_page(p);
    free_page(p1);
    free_page(p2);
}

// LAB2: below code is used to check the first fit allocation algorithm
// NOTICE: You SHOULD NOT CHANGE basic_check, default_check functions!
static void
default_check(void) {
    int count = 0, total = 0;// 页数和空闲页数
    list_entry_t *le = &free_list;
    // 遍历并验证每个块的属性
    while ((le = list_next(le)) != &free_list) {
        struct Page *p = le2page(le, page_link);
        assert(PageProperty(p));
        count ++, total += p->property;
    }
    assert(total == nr_free_pages());

    basic_check();

    // 分配p0
    struct Page *p0 = alloc_pages(5), *p1, *p2;
    assert(p0 != NULL);
    assert(!PageProperty(p0));

    // 初始化free_list并清空
    list_entry_t free_list_store = free_list;
    list_init(&free_list);
    assert(list_empty(&free_list));
    assert(alloc_page() == NULL);

    // 保存nr_free的值
    unsigned int nr_free_store = nr_free;
    nr_free = 0;

    // 下面是各种释放，验证分配态
    free_pages(p0 + 2, 3);
    assert(alloc_pages(4) == NULL);
    assert(PageProperty(p0 + 2) && p0[2].property == 3);
    assert((p1 = alloc_pages(3)) != NULL);
    assert(alloc_page() == NULL);
    assert(p0 + 2 == p1);

    p2 = p0 + 1;
    free_page(p0);
    free_pages(p1, 3);
    assert(PageProperty(p0) && p0->property == 1);
    assert(PageProperty(p1) && p1->property == 3);

    assert((p0 = alloc_page()) == p2 - 1);
    free_page(p0);
    assert((p0 = alloc_pages(2)) == p2 + 1);

    free_pages(p0, 2);
    free_page(p2);

    assert((p0 = alloc_pages(5)) != NULL);
    assert(alloc_page() == NULL);

    assert(nr_free == 0);
    nr_free = nr_free_store;

    free_list = free_list_store;
    free_pages(p0, 5);

    le = &free_list;
    while ((le = list_next(le)) != &free_list) {
        struct Page *p = le2page(le, page_link);
        count --, total -= p->property;
    }
    assert(count == 0);
    assert(total == 0);
}
//这个结构体在
const struct pmm_manager default_pmm_manager = {
    .name = "default_pmm_manager",
    .init = default_init,
    .init_memmap = default_init_memmap,
    .alloc_pages = default_alloc_pages,
    .free_pages = default_free_pages,
    .nr_free_pages = default_nr_free_pages,
    .check = default_check,
};

